The present embodiments relate to Reed-Solomon encoding, and to circuitry for performing such encoding, particularly on an integrated circuit.
Many modern applications encode data prior to transmission of the data on a network using error-correcting codes such as Reed-Solomon codes. Such codes are capable of providing powerful error correction capability. For example, a Reed-Solomon code of length n and including n−k check symbols may detect any combination of up to 2t=n−k erroneous symbols and correct any combination of up to t symbols.
Most known techniques for Reed-Solomon encoding are based on polynomial division. The direct application of this method allows for calculation of check symbols, which are sometimes also referred to as parity check symbols, based on the input of one data symbol at a time. With k symbols in a message word, k clock cycles are needed to calculate n−k check symbols. By substitution, it may be possible to calculate the check symbols based on the input of a number of data symbols at once, but the feedback nature of such a calculation means that the critical path grows with each additional parallel input symbol, and the encoder operational frequency is decreased quickly.
Moreover, increasing communications, storage, and processing demands require ever more efficient error correction including Reed-Solomon forward error correction (FEC). Consequently, it is desirable to provide improved mechanisms for implementing error correction.